package tut.binnaryTree.base;

public class BinaryTree {

	public Node root; // ptr to the root of the Binary

	public static final int LEFT_NODE_RIGHT = 1;
	public static final int NODE_LEFT_RIGHT = 2;
	public static final int LEFT_RIGHT_NODE = 3;

	public BinaryTree() {
		root = null;
	}

	public boolean lookup(int key) {
		return lookup(root, key);
	}

	private boolean lookup(Node n, int key) {
		if (n == null) {
			return false;
		}

		if (n.getKey() == key) {
			return true;
		}

		if (key - n.getKey() < 0) {
			// key < this node's key; look in left subtree
			return lookup(n.getLeft(), key);
		}

		else {
			// key > this node's key; look in right subtree
			return lookup(n.getRight(), key);
		}
	}

	public void insert(int key) throws DuplicateException {
		root = insert(root, key);
	}

	private Node insert(Node n, int key) throws DuplicateException {
		if (n == null) {
			return new Node(key, null, null);
		}

		if (n.getKey() == key) {
			throw new DuplicateException("duplicate key " + key);
		}

		if (key - n.getKey() < 0) {
			// add k to the left subtree
			n.setLeft(insert(n.getLeft(), key));
			return n;
		}

		else {
			// add k to the right subtree
			n.setRight(insert(n.getRight(), key));
			return n;
		}
	}

	public void delete(int key) {
		root = delete(root, key);
	}

	public Node delete(Node n, int key) {
		if (n == null) {
			return null;
		}

		if (key == n.getKey()) {
			if (n.getLeft() == null && n.getRight() == null) {
				return null;
			}

			if (n.getLeft() == null) {
				return n.getRight();
			}

			if (n.getRight() == null) {
				return n.getLeft();
			}

			int smallest = getSmallest(n.getRight()).getKey();
			n.setKey(smallest);
			n.setRight(delete(n.getRight(), smallest));
			return n;
		}

		if (key - n.getKey() < 0) {
			n.setLeft(delete(n.getLeft(), key));
			return n;
		}

		else {
			n.setRight(delete(n.getRight(), key));
			return n;
		}
	}

	public Node getSmallest() {
		return getSmallest(root);
	}

	public Node getSmallest(Node n) {
		if (n == null) {
			return null;
		}

		if (n.getLeft() == null) {
			return n;
		} else {
			return getSmallest(n.getLeft());
		}
	}

	public Node getRightSmallest() {
		return getSmallest(root.getRight());
	}

	public int heightOfBinaryTree(Node node) {
		if (node == null) {
			return 0;
		} else {
			return 1 + Math.max(heightOfBinaryTree(node.getLeft()),
					heightOfBinaryTree(node.getRight()));
		}
	}

	public int getHeight() {
		if (root == null) {
			return 0;
		} else {
			return 1 + Math.max(heightOfBinaryTree(root.getLeft()),
					heightOfBinaryTree(root.getRight()));
		}
	}

	// Có 6 phương pháp duyệt cây : NLR , LNR ; LRN ; NRL ; RNL ; RLN .
	// Ba phương pháp sau tương tự với 3 phương pháp đầu nên ta chỉ xét 3 phương
	// pháp đầu .

	public void browser(int type) {
		switch (type) {
		case LEFT_NODE_RIGHT:
			leftNodeRight(root);
			break;
		case NODE_LEFT_RIGHT:
			nodeLeftRight(root);
			break;
		case LEFT_RIGHT_NODE:
			leftRightNode(root);
			break;
		}
	}

	// a/ Node - Left - Right : preOrder duyet theo thu tu truoc
	public void nodeLeftRight(Node n) {
		if (n != null) {
			System.out.println(n.getKey());
			nodeLeftRight(n.getLeft());
			nodeLeftRight(n.getRight());
		}
	}

	// b/ Left - Node - Right : inOrder duyet theo thu tu truoc
	public void leftNodeRight(Node n) {
		if (n != null) {
			leftNodeRight(n.getLeft());
			System.out.println(n.getKey());
			leftNodeRight(n.getRight());
		}
	}

	// c/ Left - Right - Node : postOrder duyet theo thu tu truoc
	public void leftRightNode(Node n) {
		if (n != null) {
			leftRightNode(n.getLeft());
			leftRightNode(n.getRight());
			System.out.println(n.getKey());
		}
	}

}